938. Range Sum of BST

給定一個二元搜尋樹 (BST)，找到位於範圍 [low, high] 之間的所有節點的值之和。

解題思路

• 利用 DFS（深度優先搜索）遍歷所有節點，檢查每個節點的值是否在 [low, high] 範圍內。
• 當節點值小於 low 時，表示所有左子樹的節點都比 low 小，因此可以跳過左子樹。
• 當節點值大於 high 時，表示所有右子樹的節點都比 high 大，因此可以跳過右子樹。

程式碼:

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left  # 左子節點
        self.right = right  # 右子節點

class Solution:
    def rangeSumBST(self, root: TreeNode, low: int, high: int) -> int:
        # 初始總和為0
        self.range_sum = 0

        def dfs(node):
            if not node:
                return  # 節點為空時直接返回
            # 節點值在範圍內，加入總和
            if low <= node.val <= high:
                self.range_sum += node.val
            # 節點值大於low，遞歸處理左子樹
            if node.val > low:
                dfs(node.left)
            # 節點值小於high，遞歸處理右子樹
            if node.val < high:
                dfs(node.right)

        # 呼叫深度優先搜尋函數
        dfs(root)
        return self.range_sum  

701. Insert into a Binary Search Tree

給定一個二元搜尋樹 (Binary Search Tree, BST) 的根節點和一個整數值 val，在該 BST 中插入一個值為 val 的新節點，並返回插入後的樹的根節點。輸入資料保證，原本的 BST 中不存在與 val 重複的值。

了解 BST 的插入規則：

• 在 BST 中，左子樹的所有節點值都小於根節點值。
• 右子樹的所有節點值都大於根節點值。
• 根據這個特性，我們可以比較新插入的 val 與當前節點的值，決定應該往左子樹或右子樹遞迴搜索，直到找到適合插入的位置。
  遞迴或迭代實現：

解決步驟：

1. 如果樹是空的，直接創建新節點並返回即可。
2. 遍歷樹中的每個節點，當 val 小於當前節點值時，往左子樹遞迴，當 val 大於當前節點值時，往右子樹遞迴。
3. 當左子樹或右子樹為 None 時，將新節點插入對應位置。

程式碼實現:

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

class Solution:
    def insertIntoBST(self, root: TreeNode, val: int) -> TreeNode:
        # 如果樹是空的，直接回傳新節點
        if not root:
            return TreeNode(val)
        
        # 遞迴遍歷樹找到合適的位置進行插入
        if val < root.val:
            # 如果 val 小於當前節點值，往左子樹走
            root.left = self.insertIntoBST(root.left, val)
        else:
            # 如果 val 大於當前節點值，往右子樹走
            root.right = self.insertIntoBST(root.right, val)
        
        # 回傳最終的根節點
        return root